El compilador se ve afectado por las dependencias en el programa, incluso si un riesgo HW no depende de un cauce dado
Planificar el código evita riesgos
Dependencias de datos (verdadera) (RAW, si hay un riesgo por recursos HW)
Instrucción i produce un resultado usado por la instrucción j, o
Instrucción j depende de datos de la instrucción k, y la instrucción k depende de un dato de la instrucción i.
Si son dependientes, no pueden ejecutarse en paralelo
Fácil de determinar para los registros (nombres fijos)
Difícil en el caso de la memoria:
Son iguales 100(R4) = 20(R6)?
En iteraciones diferentes de un bucle, son iguales 20(R6) = 20(R6)?
Se requiere que el compilador conozca que si R1 no cambia entonces: 0(R1) ? -8(R1) ? -16(R1) ? -24(R1)
11
PUNTO DE VISTA DEL COMPILADOR RESPECTO A LA REORDENACIÓN DEL CÓDIGO
Otro tipo de dependencia denominado dependencia de nombre: dos instrucciones que usan el mismo nombre (registro o dirección de memoria) pero que no intercambian datos
Antidependencia (WAR, si hay un riesgo por HW)
La instrucción j escribe en un registro o posición de memoria de la que otra instrucción i lee y la instrucción i se ejecuta primero
Dependencia de Salida (WAW, si hay un riesgo por HW )
La instrucción i y la instrucción j escriben en el mismo registro o posición de memoria; el orden de las instrucciones debe de ser conservado.
12
PUNTO DE VISTA DEL COMPILADOR RESPECTO A LA REORDENACIÓN DEL CÓDIGO
13
1 Loop: LD F0, 0 (R1)
2 ADDD F4, F0, F2
3 SD 0 (R1), F4 ;eliminadas SUBI & BNEZ
4 LD F0, -8 (R1)
2 ADDD F4, F0, F2
3 SD -8 (R1) ,F4 ;eliminadas SUBI & BNEZ
7 LD F0, -16 (R1)
8 ADDD F4, F0, F2
9 SD -16 (R1), F4 ;eliminadas SUBI & BNEZ
10 LD F0, -24 (R1)
11 ADDD F4, F0, F2
12 SD -24 (R1), F4
13 SUBI R1, R1, #32 ;cambiado a 4*8
14 BNEZ R1, LOOP
15 NOP
Cómo eliminarlas?
DÓNDE ESTÁN LAS DEPENDENCIAS DE NOMBRE?
14
1 Loop: LD F0, 0 (R1)
2 ADDD F4, F0, F2
3 SD 0 (R1), F4 ;eliminadas SUBI & BNEZ
4 LD F6, -8 (R1)
5 ADDD F8, F6, F2
6 SD -8 (R1), F8 ; eliminadas SUBI & BNEZ
7 LD F10, -16 (R1)
8 ADDD F12, F10, F2
9 SD -16 (R1), F12 ; eliminadas SUBI & BNEZ
10 LD F14, -24 (R1)
11 ADDD F16, F14, F2
12 SD -24 (R1), F16
13 SUBI R1, R1, #32 ;cambiado a 4*8
14 BNEZ R1, LOOP
15 NOP
Haciendo un “renombrado de registros” ( “register renaming”)
DÓNDE ESTÁN LAS DEPENDENCIAS DE NOMBRE?
Ejemplo: Dónde están las dependencias de datos? (A,B,C distintas y no se solapan)
for (i=1; i<=100; i=i+1) { A[i] = A[i-1] + C[i-1]; /* S1 */ B[i] = B[i-1] + A[i];} /* S2 */
S1 utiliza un valor calculado por S1 en una iteración anterior, dado que la iteración i calcula A[i] el cual es leído en la iteración i+1(A[i-1]). Lo mismo le ocurre a S2 para B[i] y B[i-1].
Esto es una dependencia acarreada (loop-carried dependence): entre iteraciones
Esto implica que las iteraciones son dependientes, y no pueden ser ejecutadas en paralelo
No es el caso del ejemplo anterior: cada iteración era independiente
Por otro lado S2 utiliza el valor A[i] calculado por S1 en la misma iteración.
No es acarreada
Se pueden ejecutar en paralelo varias iteraciones del bucle siempre que las dos instrucciones se ejecuten juntas
15
DEPENDENCIAS ACARREADAS
Verificar si se puede mover S.D después de DSUBI y BNEZ, y encontrar la cantidad para ajustar el offset del S.D
Determinar si el desenrollado del bucle será útil: se determina qué iteraciones del bucle son independientes
Renombrar los registros para evitar dependencias de nombre
Eliminar los tests extras e instrucciones de salto, y ajustar la terminación del bucle y el código que se itera
Determinar los loads y stores en el bucle desenrollado que pueden ser intercambiados, para lo que se observa qué loads y stores de diferentes iteraciones son independientes
requiere analizar las direcciones de memoria y buscar para que no haya referencias a la misma dirección de memoria.
Planificar el código, preservando cualquier dependencia que sea necesaria para obtener el mismo resultado que el código original
16
PASOS DEL COMPILADOR PARA DESENRROLLAR
17
Ejemplo
if p1 {S1;};
if p2 {S2;};
S1 es dependiente de control respecto a p1
S2 es dependiente de control respecto a p2 pero no respecto a p1.
Dos restricciones (obvias) en las dependencias de control:
Una instrucción que es dependiente de control respecto a un branch no puede moverse antes (fuera) del branch para que su ejecución no este controlada por el branch.
Una instrucción que no es dependiente de control respecto a un branch no puede ser movida después (dentro) del branch ya que su ejecución entonces es controlada por el branch.
DEPENDENCIAS DE CONTROL
Observación: si las iteraciones de los bucles son independientes, entonces es posible conseguir un mayor ILP tomando instrucciones de diferentes iteraciones
Software pipelining: reorganiza los bucles de forma que cada iteración está formada por instrucciones elegidas de diferentes iteraciones del bucle original (~ Tomasulo in SW)
18
OTRA POSIBILIDAD: SOFTWARE PIPELINING
19
Desenrollado simbólico del bucle
Maximiza resultado
Código más pequeño que con desenrollado convencional
Llena y vacía el cauce sólo una vez por bucle, en vez de una vez por iteración desenrollada en el caso de desenrollado del bucle
SOFTWARE PIPELINING
20
Partimos de un código ensamblador con dependencias de flujo
ADDI R6, R0, #40
Loop:
ADD R1, R2, R3
SUBI R4, R1, R0
SD R4, 0(R6)
SUBI R6, R6, #8
BNEZ R6, loop
SOFTWARE PIPELINING: EJEMPLO 1
21
Primero identificamos qué instrucciones se van a repetir (como al desenrollar)
Estas instrucciones se tienen que ejecutar secuencialmente por las dependencias
ADDI R6, R0, #40
Loop:
ADD R1, R2, R3
SUBI R4, R1, R0
SD R4, 0(R6)
SUBI R6, R6, #8
BNEZ R6, loop
SOFTWARE PIPELINING: EJEMPLO 1
22
Es posible simular una segmentación a nivel software, dado que no existe dependencia entre instrucciones de distintas iteraciones
SOFTWARE PIPELINING: EJEMPLO 1
23
De aquí podemos sacar un nuevo patrón de instrucciones que se repiten, aparte de un prólogo y epílogo.
SOFTWARE PIPELINING: EJEMPLO 1
24
Nuevamente podemos reordenar el código, aún sin ser un bucle
ADD R1, R2, R3
SUBI R4, R1, R0
ADD R1, R2, R3
SD R4, 0(R6)
SUBI R4, R1, R0
ADD R1, R2, R3
SD R4, -8(R6)
SUBI R4, R1, R0
SD R4, -16(R6)
SOFTWARE PIPELINING: EJEMPLO 1
25
Si añadimos el bucle, quedaría así (cuidado con los índices en los accesos a memoria)
ADDI R6, R0, #40
ADD R1, R2, R3
SUBI R4, R1, R0
ADD R1, R2, R3
loop: SD R4, 0(R6)
SUBI R4, R1, R0
ADD R1, R2, R3
SUBI R6, R6, #8
BNEZ R6, loop
SD R4, -8(R6)
SUBI R4, R1, R0
SD R4, -16(R6)
SOFTWARE PIPELINING: EJEMPLO 1
Antes: Desenrollando 3 veces
1 L.D F0,0(R1)
2 ADD.D F4,F0,F2
3 S.D 0(R1),F4
4 L.D F6,-8(R1)
5 ADD.D F8,F6,F2
6 S.D -8(R1),F8
7 L.D F10,-16(R1)
8 ADD.D F12,F10,F2
9 S.D -16(R1),F12
10 DSUBUI R1,R1,#24
11 BNEZ R1,LOOP
26
Después: Software Pipelined
1 S.D 0(R1),F4 ; Stores X[i]
2 ADD.D F4,F0,F2 ; Adds to X[i-1]
3 L.D F0,-16(R1); Loads X[i-2]
4 DSUBUI R1,R1,#8
5 BNEZ R1,LOOP
5 cycles per iteration
SOFTWARE PIPELINING : EJEMPLO 2
Falta el código de comienzo y finalización (start-up & finish-up code)
Comienzo: instrucciones que corresponden a las iteraciones 1 y 2 que no se han ejecutado
L.D iteraciones 1 y 2
ADD.D iteración 1
Finalización: instrucciones que corresponden a las dos últimas iteraciones que no se han ejecutado
ADD.D última iteración
S.D dos últimas iteraciones
27
SOFTWARE PIPELINING : EJEMPLO
Por qué en HW y en run time?
Porque funciona bien cuando no se conocen las dependencias reales en tiempo de compilación
El compilador es más simple
El código para una máquina funciona bien en otra
Idea clave: permitir que instrucciones situadas después de una detención prosigan su ejecución
DIVD F0,F2,F4
ADDD F10,F0,F8
SUBD F12,F8,F14
Permitir la ejecución out-of-order execution => finalización out-of-order
Aparece en el Scoreboard de la máquina CDC 6600 en 1963
28
ESQUEMAS HW: PARALELISMO DE INSTRUCCIÓN
 Página anterior | Volver al principio del trabajo | Página siguiente  |